#include <iostream>
#include <string>

using std::string;

class Solution {
  public:
    bool isMatch(string s, string p) { isMatch(s, p, 0, 0); }

    bool isMatch_(string s, string p) {
        for (int i = 0; i < s.size(); ++i) {
            if (match_once(s, p, i)) return true;
        }
        return false;
    }

    bool match_once(string s, string p, int si, int pi = 0) {
        while (pi < p.size() and si < s.size()) {
            // need rewrite
            if (p[pi] == s[si]) {
                ++pi, ++si;
            } else if (p[pi] == '.') {
                if (p[pi + 1] == '*') return match_once(s, p, si, pi + 2);
                ++pi, ++si;
            } else if (p[pi] == '*') {
                if (p[pi + 1] == s[si]) {
                    if (match_once(s, p, si, pi + 1)) {
                        return true;
                    }
                    ++si;
                } else if (p[pi + 2] == '*') {
                    if (match_once(s, p, si, pi + 2)) return true;
                } else if (p[pi - 1] == s[si]) {
                    ++si;
                } else {
                    return false;
                }
            } else if (p[pi + 1] == '*') {
                pi += 2;
            } else {
                return false;
            }
        }
        return true;
    }

    bool isMatch(string s, string p, int s_start, int p_start) {
        int ok_size = p_start;
        for (int i = s_start; i < s.size(); ++i) {
            if (s[i] == p[ok_size]) {
                // 无需考虑s中存在特殊字符
                ++ok_size;
            } else {
                if (p[ok_size] == '.') {  // 判断是否是通配符
                    if (ok_size + 1 < p.size() && p[ok_size + 1] == '*') {
                        // 出现.* 后， 只要s 后面部分出现p 后面部分即为真
                        return isMatch(s, p, i + 1, ok_size + 2);
                    }
                    ++ok_size;
                    // 判断这个是否可以跳过
                } else if (p[ok_size] == '*') {
                    if (s[i] == p[ok_size + 1]) {
                        // 需要考虑回溯
                    } else if (s[i] != p[ok_size - 1]) {
                        ok_size = p_start;
                        // 可能需要考虑 s[i] 是否等于 p[0] (p[p_start])
                        // 下面也是
                        // --i 可以解决一部分问题， 考虑会不会造成死循环
                    }
                } else if (ok_size + 1 < p.size() && p[ok_size + 1] == '*') {
                    ok_size += 2;
                } else {
                    ok_size = p_start;
                }
            }
            if (ok_size == p.size()) return true;
        }
        return false;
    }
};

void print(bool flag) {
    if (flag) {
        std::cout << "true\n";
    } else {
        std::cout << "false\n";
    }
}

int main() {
    std::string s{"aab"};
    std::string p{"c*a*b"};
    Solution solu;
    print(solu.match_once(s, p, 0));
    return 0;
}

class Solution_new {
  public:
    bool isMatch(string s, string p) {
        string new_p;
        for (int i = 0; i < p.size(); ++i) {
            if (i + 3 < p.size() and p[i + 1] == '*' and p[i + 3] == '*' and p[i] == p[i + 2]) {
                i++;
            } else {
                new_p.push_back(p[i]);
            }
        }
        return isMatch(s, new_p, 0, 0);
    }

    bool isMatch(string s, string p, int si, int pi) {
        if (si == s.size()) {
            if (pi == p.size())
                return true;
            else if (pi + 1 < p.size() and p[pi + 1] == '*')
                return isMatch(s, p, si, pi + 2);
            else
                return false;
        }
        bool matched = p[pi] == '.' or p[pi] == s[si];
        if (pi + 1 < p.size() and p[pi + 1] == '*') {
            if (matched)
                return isMatch(s, p, si + 1, pi) or isMatch(s, p, si, pi + 2);
            else
                return isMatch(s, p, si, pi + 2);
        } else if (matched) {
            return isMatch(s, p, si + 1, pi + 1);
        }
        return false;
    }
};
